/*
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
*/
typedef int DataType;

struct NODE 
{
    DataType value;
    struct NODE * next;
};


typedef struct
{
    struct NODE * head;
    struct NODE * tail;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

    // 创建k+1个节点
MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue * CQ = (MyCircularQueue * )malloc(sizeof(MyCircularQueue) * 1);
    CQ->head = NULL;
    CQ->tail = NULL;
    if(CQ->head == NULL)
    {
        struct NODE * NewNode = (struct NODE * )malloc(sizeof(struct NODE ) * 1);
        if(NewNode == NULL)
        {
            printf("malloc fail\n ");
            exit(-1);
        }
        CQ->head = NewNode;
        CQ->tail = NewNode;
    }
    while(k--)
    {
        struct NODE * NewNode = (struct NODE * )malloc(sizeof(struct NODE ) * 1);
        if(NewNode == NULL)
        {
            printf("malloc fail\n ");
            exit(-1);
        }
        
        CQ->tail->next = NewNode;
        CQ->tail = NewNode;
    }
    CQ->tail->next = CQ->head;
    CQ->tail = CQ->head;
    return CQ;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj)) // 满了不增
        return false;
    obj->tail->value = value;
    obj->tail = obj->tail->next;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) // 空了不删
        return false;
    obj->head = obj->head->next;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) 
        return -1;
    return obj->head->value;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) 
        return -1;
    struct NODE* cur = obj->head->next;
    while(cur->next != obj->tail)
        cur = cur->next;
    // 返回上一个节点的value值
    return cur->value;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return  obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->tail->next == obj->head;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    struct NODE* cur = obj->head->next;
    while(cur != obj->head)
    {
        struct NODE * temp = cur->next;
        free(cur);
        cur = temp;
    }
    free(cur);

    free(obj);
}


//  测试样例
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/